package util ;

import java.io.Serializable ;
import java.util.Arrays ;
import java.util.Collection ;
import java.util.HashSet ;
import java.util.Iterator ;
import java.util.Set ;

/**
 * a hierarchical set is a set whose elements are a union of its own elements and its parent's elements. a
 * hierarchical set is immutable. this is subject to changes, not an interface guarantee. hierarchical sets
 * cannot be iterated or queried for size: they are simply checked for containment. they can, though, be
 * shallow-copied to a set form, if needed.
 *
 * the empty set is the the default parent of a parent-less hierarchical set.
 *
 * hierarchical set guarantees to keep duplicate elements if they are in different sets in the hierarchy (i.e.
 * child and ancestor) and to NOT keep duplicates if they are in the exact same set in the hierarchy.
 *
 * @param <E> element type.
 */
public class HierarchicalSet<E> implements Set<E>, Serializable
{
	/*
	 * implementation: if 'a' belongs to B, a child of A, then 'a' could also be added to A and it is legal.
	 * therefore, we allow duplications, we just don't present them.
	 */

	@SuppressWarnings("unchecked")
	private static Set EMPTY_SET = new HashSet() ;

	/***/
	private static final long serialVersionUID = -7359100857955001776L ;

	private Set<E> elements ;
	private Set<E> parent ;

	/**
	 * @param <E> type of elements in the sets.
	 * @param s1 a set.
	 * @param s2 a set.
	 * @return 'true' if s1 and s2 are disjoint, and 'false' otherwise.
	 */
	public static <E> boolean areDisjoint(final Set<E> s1, final Set<E> s2)
	{
		for (final E i: s2)
		{
			if (s1.contains(i))
			{
				return false ;
			}
		}
		/*
		 * no need to check symmetry: if s2 contains an element 'e' which is in s1, the previous loop would
		 * have found it.
		 */
		return true ;
	}

	/**
	 * @param <R> type of the set elements.
	 * @return the empty set.
	 */
	@SuppressWarnings("unchecked")
	public static <R> Set<R> emptySet()
	{
		return HierarchicalSet.EMPTY_SET ;
	}

	/**
	 * @param <E> type of elements in the set.
	 * @param singleton set to extract element from.
	 * @return the only element in the singleton.
	 * @pre singleton.size() == 1.
	 */
	public static <E> E getElementFromSingleton(final Set<E> singleton)
	{
		return singleton.iterator().next() ;
	}

	/**
	 * create a parent set.
	 * @param elements elements of this set.
	 * @post this.getElements() = elements.
	 * @post this.getParent() = emptySet().
	 */
	public HierarchicalSet(final Collection<E> elements)
	{
		this.parent = HierarchicalSet.emptySet() ;
		this.elements = new HashSet<E>(elements) ;
	}

	/**
	 * create a parent set.
	 * @param elements elements of this privilege.
	 * @post this.getElements() = elements.
	 * @post this.getParent() = emptySet().
	 */
	public HierarchicalSet(final E... elements)
	{
		this(Arrays.asList(elements)) ;
	}

	/**
	 * create a child set.
	 * @param parent parent of this set.
	 * @param elements elements of this set.
	 * @post this.getElements() = elements
	 * @post this.getParent() = parent. parent is not copied, but rather shared.
	 */
	public HierarchicalSet(final Set<E> parent, final Collection<E> elements)
	{
		this.parent = parent ;
		this.elements = new HashSet<E>(elements) ;
	}

	/**
	 * create a child set.
	 * @param parent parent of this set.
	 * @param elements elements of this set.
	 * @post this.getElements() = set.getElements()
	 * @post this.getParent() = parent. parent is not copied, but rather shared.
	 *
	 * note that if there are no elements, copy constructor is called. if you wish to create a child which
	 * does not extend its parent, use the HierarchicalSet(parent, collection) constructor.
	 */
	public HierarchicalSet(final Set<E> parent, final E... elements)
	{
		this(parent, Arrays.asList(elements)) ;
	}

	/**
	 * @see java.util.Set#add(java.lang.Object)
	 * @post the element is added to the bottom set in the hierarchy.
	 */
	public boolean add(final E element)
	{
		if (this.getParent().contains(element))
		{
			return false ;
		}
		else
		{
			return this.elements.add(element) ;
		}
	}

	/**
	 * @see java.util.Set#addAll(java.util.Collection)
	 */
	@Override
	public boolean addAll(final Collection<? extends E> collection)
	{
		boolean result = false ;
		for (final E element: collection)
		{
			result |= this.add(element) ;
		}
		return result ;
	}

	/**
	 * all elements are cleared, and this set will lose its parent.
	 * @see java.util.Set#clear()
	 */
	@Override
	public void clear()
	{
		this.parent = HierarchicalSet.emptySet() ;
		this.elements.clear() ;
	}

	/**
	 * @param element element to test for.
	 * @return 'true' if this set contains 'element' and 'false' otherwise.
	 */
	public boolean contains(final Object element)
	{
		boolean result = false ;
		result |= this.elements.contains(element) ;
		result |= this.getParent().contains(element) ;
		return result ;
	}

	/**
	 * @see java.util.Set#containsAll(java.util.Collection)
	 */
	@Override
	public boolean containsAll(final Collection<?> collection)
	{
		return this.getElements().containsAll(collection) ;
	}

	/**
	 * set1 == set2 iff both sets has the exact same elements.
	 * @see java.lang.Object#equals(java.lang.Object)
	 */
	@SuppressWarnings("unchecked")
	@Override
	public boolean equals(final Object obj)
	{
		return (obj instanceof Set && this.getElements().equals(obj)) ;
	}

	/**
	 * @return parent of this set. 'null' if this set has no parent.
	 */
	public Set<E> getParent()
	{
		return this.parent ;
	}

	/**
	 * @see java.lang.Object#hashCode()
	 */
	@Override
	public int hashCode()
	{
		return this.getElements().hashCode() ;
	}

	/**
	 * @see java.util.Set#isEmpty()
	 */
	@Override
	public boolean isEmpty()
	{
		return this.size() == 0 ;
	}

	/**
	 * @see java.util.Set#iterator()
	 */
	@Override
	public Iterator<E> iterator()
	{
		return this.getElements().iterator() ;
	}

	/**
	 * if the element is in the parent, a copy of the parent is made, effectively splitting the hierarchy tree
	 * into 2 separate trees.
	 * @see java.util.Set#remove(java.lang.Object)
	 */
	@Override
	public boolean remove(final Object element)
	{
		boolean isRemoved = false ;
		if (this.elements.contains(element))
		{
			isRemoved |= this.elements.remove(element) ;
		}
		if (!isRemoved)
		{
			this.parent = new HashSet<E>(this.getParent()) ;
			isRemoved |= this.getParent().remove(element) ;
		}
		return isRemoved ;
	}

	/**
	 * if the element is in the parent, a copy of the parent is made, effectively splitting the hierarchy tree
	 * into 2 separate trees.
	 * @see java.util.Set#removeAll(java.util.Collection)
	 */
	@Override
	public boolean removeAll(final Collection<?> collection)
	{
		boolean result = false ;
		for (final Object element: collection)
		{
			result |= this.remove(element) ;
		}
		return result ;
	}

	/**
	 * if there are elements to remove from the parent, a copy of the parent is made, effectively splitting
	 * the hierarchy tree into 2 separate trees.
	 * @see java.util.Set#retainAll(java.util.Collection)
	 */
	@Override
	public boolean retainAll(final Collection<?> collection)
	{
		boolean retainedChild, retainedParent ;
		retainedChild = this.elements.retainAll(collection) ;

		/*
		 * if the parent is needs to be modified as well, make a private copy of it. to be safe, we modify the
		 * copy rather than the parent.
		 */
		final Set<E> alternativeParent = new HierarchicalSet<E>(this.getParent()) ;
		retainedParent = alternativeParent.retainAll(collection) ;
		if (!alternativeParent.equals(this.getParent()))
		{
			this.parent = alternativeParent ;
		}

		return retainedChild || retainedParent ;
	}

	/**
	 * @see java.util.Set#size()
	 */
	@Override
	public int size()
	{
		return this.getElements().size() ; // if we just summed up the sizes we'd count duplicates.
	}

	/**
	 * @see java.util.Set#toArray()
	 */
	@Override
	public Object[] toArray()
	{
		return this.getElements().toArray() ;
	}

	/**
	 * @see java.util.Set#toArray(T[])
	 */
	@Override
	public <T> T[] toArray(final T[] array)
	{
		return this.getElements().toArray(array) ;
	}

	/**
	 * same as its elements.
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString()
	{
		return this.getElements().toString() ;
	}

	/**
	 * @return set of elements in the entire hierarchy.
	 */
	protected Set<E> getElements()
	{
		final Set<E> result = new HashSet<E>(this.elements) ;
		result.addAll(this.getParent()) ;
		return result ;
	}
}
